package base.sort.separate;

import base.sort.IImmutableSorter;
import static java.util.stream.Collectors.toList;
import java.util.List;

/**
 * 不是对半拆分的排序
 * 快速排序，比x小 x 比x大
 */
public class QuickSortImmutable implements IImmutableSorter {
    @Override
    public List<Integer> sort(List<Integer> A) {
        return this.quickSort(A);
    }

    private List<Integer> quickSort(List<Integer> A) {
        // 递归的退出条件
        if (A.size() <= 1) {
            return A;
        }

        // ｜---left---｜x｜---right---|
        var x = A.get(0);
        var left = A.stream().filter(a -> a < x)
                .collect(toList());
        var mid = A.stream().filter(a -> a.equals(x))
                .collect(toList());
        var right = A.stream().filter(a -> a > x)
                .collect(toList());
        left = quickSort(left);
        right = quickSort(right);
        left.addAll(mid);
        left.addAll(right);
        return left;
    }
}
